// Copyright 2011 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

/*
-- xGo: Go language extensions: Type parametrized declarations proposal draft

Both the extended language and the draft is informally named 'xGo' and/or 'xgo'
respectively and interchangeably. In the same time 'xgo' is also the name of an
accompanying tool, a toy implementation of xgo.

TODO TOC

-- 1. Scanner issues

---- 1.1 Lexical grammar

Two new tokens are recognized by the lexer. They are '«' (U+00AB) and '»'
(U+00BB).

---- 1.2 Semicolon rules

The '»' causes semicolon injection subject to the same rules as e.g. ')' or '}'
do already.

-- 2. Parser issues

---- 2.1 Language syntax

No new keywords are introduced.

------ 2.1.1 New productions

Two new productions are accepted by the parser:

 XgoParameters = "«" identifier { "," identifier } [ "," ] "»" .
 XgoArguments  = "«" Type { "," Type } [ "," ] "»" .

------ 2.1.2 Modified productions

Xgo's central concept is to allow expansion/specialization of parametrized
declarations using types, and only types, as arguments. Modifications of the
language syntax specific to each xgo declaration/use are described in the
following text.

-- 3. Xgo types

---- 3.1 Syntax

------ 3.1.1 Declaration

The TypeSpec production (http://golang.org/doc/go_spec.html#TypeSpec) is
changed to:

 TypeSpec = identifier [ XgoParameters ] Type .

A type is a xgo type if the optional xgo parameters are present in the type's
declaration:

 type (
 	t«u»	[]u		// t is a xgo type
 	v«w, x» struct {	// v is a xgo type
 		items [42]w
 		flags map[x]bool
 		cache *x
 	}
 	w	t«string»	// w is not a xgo type
 )

------ 3.1.2 Usage

The Type production (http://golang.org/doc/go_spec.html#Type) is changed to:

 Type = TypeName [ XgoArguments ] | TypeLit | "(" Type ")" .

In a type specification a type name may be optionally followed by xgo
arguments. Type name must be in that case a xgo type. The Type production is
used in many places in the language:

 // Declaration
 type t«u» type-definition

 // Few usage "place" examples
 type v t«w»
 type z func(t«a»)
 var x t«y»
 func f(arg t«a») (returns t«b») {
 	c := t«d»{...}
 	func(t«a») {...}(arg)
 	return t«b»(c)
 }

---- 3.2 Scoping

------ 3.2.1 Declaration

Xgo types do reserve a name slot in the current scope as if they would be a
standard type:

 type t u
 type t«...» definition // ERROR 't' redeclared

But they can't be resolved as a type without the specialization (the presence
of xgo arguments):

 type t«u» []u

 type v t	// ERROR 't' undefined || ERROR expected xgo arguments.
 		// Other possible 't' in outer scope(s) ignored.

 type w t«int»	// OK

Xgo types are otherwise visible in inner scopes in the standard way:

 package p

 type t«u» []u

 func main() {
 	var v t«int»
 }

------ 3.2.2 Parameters

Xgo parameters are visible inside the definition of the xgo type. When the xgo
type is used (expanded/specialized) using the name of a xgo type with xgo
arguments, the respective type names used in the xgo type definition, which are
listed in the xgo parameters of that xgo type - and only those names - are
replaced by the respective xgo arguments type.

 type t«u» struct {
 	slice []u	// u is a type name, will be replaced
 	u     v		// u is not a type name, ignored
 }

 var x t«int»

 //TODO verify
 // expands to - says the same as:
 //
 // var x struct {
 //	slice []int
 //	u     v		// whatever v type is visible in current scope
 // }

---- 3.3 Nesting

------ 3.3.1 Declarations

The above rules allow nested xgo type declarations:

 type t«u» []u
 type v«w, x» struct {
 	item   w
 	itemsA t«w»
 	itemsB t«x»
 } 

 var z v«int, bool»

 //TODO verify
 // expands to - says the same as:
 //
 // var z struct {
 //	item   int
 //	itemsA []int
 //	itemsB []bool
 // }

The recursive declarations must be loop free (acyclic) as with
standard types.

------ 3.3.2 Arguments

The above rules allow nested xgo type arguments:

 type t«u» []u
 type v«w» struct {
 	id    int
 	index map[int]w
 }

 var z v«t«string»»

 //TODO verify
 // expands to - says the same as:
 //
 // var z struct {
 //	id    int
 //	index map[int][]string
 // }

The recursive arguments expansion must be again loop free.

---- 3.4 Self referential rule

Consider:

 type node«t» struct {
 	next  *node
 	value t
 }

 var intnode node«int»

 //TODO verify
 // expands to - says the same as:
 //
 // var intnode struct {
 //	next  *node	// ERROR 'node' undefined, outer scope ignored
 //	value int
 // }

The resolution is:

 type node«t» struct {
 	next  *node
 	value t
 }

 type intnode node«int»

 //TODO verify
 // expands to - says the same as:
 //
 // type intnode struct {
 //	next  *intnode
 //	value int
 // }

The rule used above is: Iff the xgo type is expanded in a type declaration then
the name of the xgo type becomes a "zeroth" parameter and replaced by the name
of the declared type. Another example of the same kind, but with a problem, is:

 type node«t» struct {
 	next  *node
 	value t
 }

 type intlist *node«int»

 //TODO verify
 // expands to - says the same as:
 //
 // type intlist *struct {
 //	next  *intlist	// Oops, this is probably not what was intended
 //	value int
 // }

The resolution is:

 type node«t» struct {
 	next  *node
 	value t
 }

 type intnode node«int»

 //TODO verify
 // expands to - says the same as:
 //
 // type intnode struct {
 //	next  *intnode
 //	value int
 // }

 type intlist *intnode
 var list1 intlist
 var list2 *intnode

---- 3.5 Anonymous struct fields

Given:

 type t«u» []u

Using t as an anonymous field in a struct like:

 type v struct {
 	t«int»
 	x y
 }

 //TODO verify
 // expands to - says the same as:
 // type v struct {
 // 	[]int	// ERROR expected TypeName
 //	x y
 // }

The resolution is:

 type w t«int»
 type v struct {
 	w
 	x y
 }

 //TODO verify
 // expands to - says the same as:
 // type w []int
 // type v struct {
 // 	w	// OK
 //	x y
 // }

-- 4. Xgo functions

---- 4.1 Syntax

The FunctionDecl production (http://golang.org/doc/go_spec.html#FunctionDecl)
is changed to:

 FunctionDecl = "func" identifier Signature [ Body ]           // std
              | "func" XgoParameters identifier Signature Body // xgo decl
              | "func" QualifiedIdent XgoArguments             // xgo use
 ) .

------ 4.1.1. Declaration

A function declaration is a xgo function if the xgo paramaters are present in
the function declaration:

 func«t» f(x t) {...}

------ 4.1.2. Expansion

xgo function can be expanded by using its name followed by xgo arguments. xgo
functions can be used/expanded in function declarations and as function
literals. That's comparable to xgo types (3.) which can be used/expanded in
type declarations and as type literals.

-------- 4.1.2.1 In a function declaration

This case is covered by the syntax in 4.1 (the second term of the alternation).

 func«t» double(arg t) t { return 2 * arg }

 func intdouble double«int»

 //TODO verify
 // expands to - says the same as:
 // func intdouble(arg int) int { return 2 * arg }

-------- 4.1.2.1 As a function literal

Not to be confused with expansion of xgo types which happen to be a function
type. That is already covered by section 3. and such expansion must be, as
required by the language already, followed by a function body (Body
http://golang.org/doc/go_spec.html#Body).

The FunctionLit production (http://golang.org/doc/go_spec.html#FunctionLit) is
changed to:

 FunctionLit = FunctionType Body 
             | QualifiedIdent XgoArguments .

The QualifiedIdent above must be a name of a xgo function visible in current
scope. Examples:

 // xgo type
 type lessfunc«t» func(a, b t) bool

 // body required in the function literal
 var intless = lessfunc«int» {
 	return a < b
 }	

 //TODO verify
 // expands to - says the same as:
 // var intless = func(a, b int) bool {
 // 	return a < b
 // }

 // ---- versus ----

 // xgo function
 func«t» min(a, b t) t {
 	if a < b {
 		return a
 	}
 	return b
 }

 // bellow function literals get the body expanded from the xgo func def

 var intmin = min«int»

 //TODO verify
 // expands to - says the same as:
 // var intmin = func(a, b int) int {
 // 	if a < b {
 //		return a
 //	}
 //	return b
 // }

 func main() {
 	println(min«float64»(2.78, 3.14))

 	//TODO verify
 	// expands to - says the same as:
 	// println(func(a, b float64) float64 {
 	// 		if a < b {
 	//			return a
 	//		}
 	//		return b
 	// 	}(2.78, 3.14))
 	// }

 }

---- 4.2 Scoping

Xgo functions do reserve a name slot in the current scope as if they would be a
standard function:

 func f() {}
 func«...» f definition // ERROR 'f' redeclared

But they can't be resolved as a functions without the specialization (the
presence of xgo arguments):

 func«u, v» f(x u) (y v) {}

 func v f		// ERROR 'f' undefined
 			// Possible outer scope 'f' ignored

 func w f«int, bool»	// OK

Xgo functions are otherwise visible in inner scopes in the same way as standard
functions:

 package p

 func«u» f(arg u) {...}

 func main() {
 	g := f«int»	// OK
 	g(1)
 }

-- 97. Export/import semantics

TODO

-- 98. Shared semantics

To reiterate, complete and describe more precisely:

---- 98.1 Matching of arguments and parameters

The number of xgo parameters of some declaration must be matched
by the same number of xgo arguments used when expanding/specializing it.

---- 98.2 Unused parameters

Comparable to unused variables. All xgo parameters must be used in their
respective scope (as defined earlier in the draft).

 type t«u, v» struct {
 	a int
 	b u
 } // ERROR parameter 'v' not used

But:

 type t«u, v» []u	// only 'u' used???
 func (t) m(v) {}	// OK, scope is the type AND all of its methods

 // and even
 type T«u, v» int	// static parametric type???
 func (t T) n(a u) v {}	// OK, 'u' and 'v' used here.

Chances are that the definition of the gobject type and all of its method will
not be on such a few lines and visible at once, so possibly an unused parameter
error could be difficult to spot.

---- 98.3 xgo declarations type checking

The expansion is valid only in correct context. Where a Type is permitted by
the language only a name of a xgo type can be used - but a name of an xgo
function cannot and vice versa.

-- 99. Type checking

---- 99.1 In general

If a xgo source is successfully expanded it becomes, in the first
approximation, a standard Go source.  Afterwards all the existing type checks
are performed by the compiler as it is being done now. This may lead to
surprises and it probably limits what can be expressed in xgo. But the rule is
really simple and actually nothing new is to be learned here - all and only the
existing semantic checks of the compiler are applied *after* the rewriting. If
the rewrite expands to invalid code then the definition of the used xgo
declaration is broken or the xgo tool is broken or the xgo proposal is broken.

---- 99.1 Wrt interfaces

It follows from the earlier rules, but it's probably worth a note. Any mixing
of xgo declarations/expansions and interfaces will be statically checked by the
compiler after rewriting. Xgo per se cannot introduce run time panics on type
assertions. What's better is that some things can be written using interfaces
and get rid of the run time type asserts at all. This patently useless
code uses interfaces for no good reason, but it will still be fully type
checked at compile time, regardless of all the xgo stuff involved. A smart
compiler may eventually optimize such code and produce its faster semantic
equivalent which doesn't really use interfaces.

 type face«t» interface {
 	bar(b t) bool
 }

 func«t» foo(a, b face«t») { a.bar(b) }

 type baz«t» t
 func (a baz) bar(b t) {
 	return a < b
 }

 type Int baz«int»
 func intfoo foo«Int»
 type Uint baz«uint»
 func uintfoo foo«Uint»

 func main() {
 	intfoo(Int(42), Int(24))
 	uintfoo(Uint(42), Uint(24))
 }

-- 100. Final notes

Experiments seems to indicate you're probably going to find a xgo construction
which makes sense but it will expand to a disaster. Xgo doesn't attempts to
cover everything;  the draft is considered "small". Still the space created by
all of the possible combinations when using xgo constructs is huge.

That said, it was not possible in the time available to explore it enough to
eliminate in advance all the probably remaining bad corner cases. OTOH, there
might be some places which no one has yet thought about.  Then there's the
opportunity to become a first visitor of them.

-=-=-=

TODO include in the draft:

----

No reflection issues expectable, except when a smart linker collects identical
expansions. Then a problem raises if they would have different names.

----

func name == 'init'

----

Method properties and categorization
 A: Has xgo parameters
 	func«T, U, ...» (R) m(...) {...}
 B: Receiver is a xgo parameter
 	func«R, T, ...» (R) m(...) {...} // !(B && C) && !(!A && B)
 C: Receiver is a xgo type
 	type T«U, V, ...» definition
 	func (T) m(...) {...} // no xgo params allowed, !(A && C)
 ----------------------------------
 ...	Standard method
 ..A	xgo method of a non xgo receiver type
 .B.	N/A // !A && B
 .BA	xgo method of a xgo receiver type
 C..	Gobject method (expands to type+methods)
 C.A	N/A // A && C
 CB.	N/A // B && C
 CBA	N/A // A && C, B && C

----

From the Go FAQ at http://golang.org/doc/go_faq.html#generics
"Generics are convenient but they come at a cost in complexity in the type
system and run-time"

Xgo is considered to have zero run-time cost both in terms of required
(additional) support and in the sense of run-time performance (everything xgo
related happened at compile time already).

Indirect run-time costs are possible due to code bloat if the compiler/linker
doesn't collect identical expansions scattered over the program. Note that
collecting identical, but differently named expansions can conflict with
reflection.

----

-- xxx. Built in types considerations (wrt methods)

It's always about named types:

 type T«u» []u

 func (t T) m() {} // works on T, not u so:

 type myT T«int» // works

 type t«u» struct{
 	u
 }

 func (rx t) m() {
 	println(rx.u)	// 
 }

 // dtto as for type T

----

http://research.swtch.com/2009/12/generic-dilemma.html

*/
package draft
//TODO verify ALL manual "expansions" or better yet, replace them
// by the actual output from the xgo tool
